C++에서 컨테이너 성장을 관리하는 것은 크기 (현재 요소)와 용량 (예약된 메모리) 사이의 아키텍처적 조율입니다. 연속적인 컨테이너인 vector 및 string에 도달하면 시스템은 더 큰 메모리 블록을 찾고, 모든 요소를 이동한 후 오래된 블록을 삭제합니다. 이는 비용이 큰 $O(n)$ 연산으로, 재할당반복자 무효화를 유발합니다. 이전 요소에 대한 포인터는 '행동 불능' 상태가 되어 위험해집니다. 반복자 무효화—기존 요소에 대한 포인터는 '다잉' 상태가 되며 위험해집니다.
1. 확장 전략
자주 발생하는 재할당을 피하기 위해 vector 구현체는 "버퍼" 공간을 할당합니다. 명시적으로 c.reserve(n) 명령어로 요소를 추가하지 않고 최소 용량을 설정하며, 반면 c.shrink_to_fit() 은 과잉 메모리를 운영체제에 반환하도록 요청하는 비결정적 방법입니다.
2. resize와 reserve의 차이점
비록 reserve reserve는 버퍼만 영향을 미치지만, resize(n) resize는 컨테이너의 로직을 직접 변경합니다. shrink_via resize 는 요소를 삭제하고, 확장 시 기본 초기화된 값을 추가합니다.
⚠️ 경고: 만약
resize 컨테이너를 축소하면 삭제된 요소에 대한 반복자가 무효화됩니다. 만약 확장으로 인해 재할당이 발생하면, 모든 모든 반복자가 무효화됩니다.main.py
TERMINALbash — 80x24
> Ready. Click "Run" to execute.
>
QUESTION 1
Exercise 9.34: Predict the behavior of this loop: while (iter != vi.end()) { if (*iter % 2) iter = vi.insert(iter, *iter); ++iter; }
It duplicates all odd numbers once and finishes.
It results in an infinite loop if an odd number is found.
It skips all odd numbers.
It causes a compilation error because of iterator types.
✅ Correct!
This is an infinite loop. vi.insert(iter, *iter) inserts before the current element and returns an iterator to the NEW element. The ++iter then moves back to the original odd element, repeating the process forever.❌ Incorrect
Analyze the return value of insert: it points to the newly inserted element. Incrementing once just puts you back on the original element you just processed.QUESTION 2
Exercise 10.10: Why don't generic algorithms like find or sort change the size of containers?
They operate on iterators, which provide no interface to add/remove container memory.
Changing size would be too slow for generic code.
The C++ standard forbids algorithms from using memory.
Algorithms only work on fixed-size arrays.
✅ Correct!
Algorithms are decoupled from containers. They only see iterators and can only modify the values the iterators point to; they cannot call container-specific members like push_back or erase.❌ Incorrect
Recall the 'Iterator Bridge' concept: algorithms use iterators to remain container-agnostic.QUESTION 3
Given vec has 25 elements, what happens if we call vec.resize(100) then vec.resize(10)?
Size becomes 100, then drops to 10; capacity likely stays at 100 throughout.
Size becomes 100, then 10; capacity drops to 10 immediately.
The program crashes on the second resize.
The elements from index 10-99 are moved to a temporary buffer.
✅ Correct!
resize(100) adds 75 default-initialized elements. resize(10) destroys the last 90 elements, but the allocated capacity remains 100 unless shrink_to_fit is called.❌ Incorrect
Resize shrinks the 'size', but capacity does not shrink automatically to save performance.QUESTION 4
What restriction is placed on the element type when calling the single-argument version of resize?
It must be a primitive type (int, double, etc.).
It must have a default constructor.
It must have a copy constructor.
It cannot be a const type.
✅ Correct!
Since resize(n) creates new elements to reach size n, those elements must be initialized using a default constructor.❌ Incorrect
If we don't provide an initial value, the container must know how to build a 'default' one.QUESTION 5
Exercise 10.39: What kind of iterator does a list have versus a vector?
List: Forward; Vector: Random-access
List: Bidirectional; Vector: Random-access
Both have Random-access iterators.
List: Output; Vector: Input
✅ Correct!
std::list is a doubly-linked list supporting bidirectional movement. std::vector is an array supporting pointer-like arithmetic (Random-access).❌ Incorrect
Can you do 'it + 5' on a list? No, which means it isn't random-access.Case Study: Safe Iterator Loops
Managing Growth in Real-time Applications
You are processing a vector of integers. For every odd number, you must duplicate it. You also need to maintain efficiency and avoid segmentation faults caused by container reallocation during the loop.
Q
1. Re-implement Exercise 9.34 correctly to avoid the infinite loop and handle iterator invalidation.
Solution:
To fix the loop: iter = vi.begin(); while (iter != vi.end()) { if (*iter % 2) { iter = vi.insert(iter, *iter); iter += 2; } else { ++iter; } } This works because insert returns the iterator to the new element; we advance past both the new and original elements to find the next candidate.
To fix the loop: iter = vi.begin(); while (iter != vi.end()) { if (*iter % 2) { iter = vi.insert(iter, *iter); iter += 2; } else { ++iter; } } This works because insert returns the iterator to the new element; we advance past both the new and original elements to find the next candidate.
Q
2. Rewrite the duplicate word elimination logic from § 10.2.3 to use a list instead of a vector. What changes?
Solution:
Since list does not support random-access, we cannot use generic sort. We must use lst.sort() and lst.unique() member functions. Unlike the vector version, lst.unique() actually removes elements from the list, changing its size immediately without needing a separate erase call.
Since list does not support random-access, we cannot use generic sort. We must use lst.sort() and lst.unique() member functions. Unlike the vector version, lst.unique() actually removes elements from the list, changing its size immediately without needing a separate erase call.
Q
3. Exercise 10.19: Rewrite the biggies logic to use stable_partition instead of find_if to maintain original order.
Solution:
auto wc = stable_partition(words.begin(), words.end(), [sz](const string &s) { return s.size() >= sz; }); This reorders the container such that all elements meeting the criteria come first, returning an iterator to the first element that does NOT meet the criteria.
auto wc = stable_partition(words.begin(), words.end(), [sz](const string &s) { return s.size() >= sz; }); This reorders the container such that all elements meeting the criteria come first, returning an iterator to the first element that does NOT meet the criteria.